package version2024.medium;

import java.util.Scanner;

/**
 * @author sunhl
 * @Description: HJ52 计算字符串的编辑距离  字符串, 动态规划
 * @Date: created in 2025/1/2 星期四 17:31
 * @Modified By:
 */
public class HJ52_CalculatingEditDistanceOfString {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            // 读取第一个字符串
            String a = in.next();
            // 读取第二个字符串
            String b = in.next();

            // abcdefg
            // abcdef
            //       a b c d e f g
            //     0 1 2 3 4 5 6 7
            //   0 0 1 2 3 4 5 6 7
            // a 1 1 0 1 2 3 4 5 6
            // b 2 2 1 0 1 2 3 4 5
            // c 3 3 2 1 0 1 2 3 4
            // d 4 4 3(2)1 0 1 2 3
            // e 5 5 4 3 2 1 0 1 2
            // f 6 6 5 4 3 2 1 0 1

            // 设置dp数组, dp[i][j]表示字符串A的前i个字符与字符串B的前j个字符相同所需要的编辑距离
            // 0位不使用, 从1开始看
            // 第0行中每列值含义:
            // 以第0行第2列dp[0][2]为例，表示由 空字符串 变成 'ab' 需要的编辑次数，显然在空字符串中执行两次添加操作即可，所以填2，第0行其他列以此类推
            // 第0列每行的含义:
            // 以第2行第0列dp[2][0]为例，表示由 字符串'ab' 变成 空字符串 需要的编辑次数，显然对'ab'执行两次删除操作即可，所以填2，第0列其他行以此类推
            // 其他空格处含义:
            // 以第2行第4列dp[2][4]为例(加括号的)，其代表'ab'变'abcd'操作
            // 相对于左边空格的'abcd'变'a'操作上再执行一次添加'b'操作, 即3 + 1
            // 相对于上边空格的'abc'变'ab'操作上再执行一次删除'd'操作, 即1 + 1
            // 相对于左上角空格的'abc'变'a'操作上再执行一次替换'd'变'b'操作, 即 2 + 1
            // 取以上3种情况中最小的
            int[][] dp = new int[a.length() + 1][b.length() + 1];

            // baseCase, 当一个字符串为空时，编辑距离等于另一个字符串的长度
            for (int i = 0; i <= a.length(); i++) {
                dp[i][0] = i;
            }
            for (int i = 0; i <= b.length(); i++) {
                dp[0][i] = i;
            }

            for (int i = 1; i <= a.length(); i++) {
                for (int j = 1; j <= b.length(); j++) {
                    // a[i]==b[j]，这种情况下，我们不需要进行编辑
                    if (a.charAt(i - 1) == b.charAt(j - 1)) {
                        dp[i][j] = dp[i - 1][j - 1];
                    } else {
                        // a[i]!=b[j]，如果两个字符不相等，我们有三种处理方式：
                        // 替换字符串b，编辑距离为dp[i-1][j-1]+1；
                        // 插入一个字符与其相等，则编辑距离为dp[i-1][j]+1；
                        // 删除该字符，编辑距离为dp[i][j-1]+1，三者取其小即可
                        dp[i][j] = Math.min(dp[i - 1][j] + 1, Math.min(dp[i - 1][j - 1] + 1,
                                dp[i][j - 1] + 1));
                    }
                }
            }

            System.out.println(dp[a.length()][b.length()]);
        }
    }
}
